package pishen;

import java.util.Collection;
import java.util.Iterator;
import java.util.Map;

import edu.uci.ics.jung.algorithms.cluster.WeakComponentClusterer;
import edu.uci.ics.jung.algorithms.filters.FilterUtils;
import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath;
import edu.uci.ics.jung.graph.Graph;

public class ShortestPathCalculator<V, E> {
	
	private Graph<V, E> graph;
	private double diameter; 
	private double averageDistance;
	
	//constructor
	public ShortestPathCalculator(Graph<V, E> g){
		this.graph = g;
		this.diameter = -1;
		this.averageDistance = -1;
	}

	//calculator
	private void CalculateDistance(){
		/*
		// collect connected component
		WeakComponentClusterer<V,E> wcc = new WeakComponentClusterer<V,E>();
        Collection<Graph<V,E>> ccs = FilterUtils.createAllInducedSubgraphs(wcc.transform(graph),graph);
		
        // find giant connected component 
        double gccVertexCount = 0 ;
        Graph<V,E> gcc = null;
        for(Graph<V,E> g : ccs){
        	if(g.getVertexCount() > gccVertexCount){ 
        		gcc = g ; 
        		gccVertexCount = Math.max(gccVertexCount , g.getVertexCount());
        	}	
        }
        
        */
		
        // do BFS algorithm
		
		
        UnweightedShortestPath<V, E> alg = new UnweightedShortestPath<V,E>(graph);
        
        
	
		Collection<V> vertices = graph.getVertices();
		Iterator<V> it = vertices.iterator();
		double lengthSum = 0;
		double maxLength = 0;
		double num =0;
		
		Iterator<V> it2 = null;
		V tmp = null;
		Map<V, Number> distances = null;
		V tmp2 = null;
		
		
		
		//sum of shortest path length
		while (it.hasNext()){
			it2 = vertices.iterator();
			tmp = it.next();
			distances = alg.getDistanceMap(tmp);
			tmp2 = it2.next();
			
			while (tmp != tmp2 && it2.hasNext()){
				tmp2 = it2.next();
			}
			
			while (it2.hasNext()){
				tmp2 = it2.next();
				if (distances.containsKey(tmp2)){
					double length = distances.get(tmp2).doubleValue();
					lengthSum += length;
					maxLength = Math.max(maxLength, length);
					num += 1;
				}
			}
			
			System.gc();
			
			
		}
		
		
		
		num += graph.getVertexCount();
		
		
		averageDistance =  lengthSum/num;
		diameter = maxLength;
		
		
		
	
	}
	
	public double getAverageDistance(){
		if (averageDistance == -1){
			CalculateDistance();
		}
		double i = averageDistance;
		averageDistance = -1;
		return i;
	}
	
	public double getDiameter(){
		if (diameter == -1){
			CalculateDistance();
		}
		double i = diameter;
		diameter = -1;
		return i;
	}
	
}
